/*
 * @lc app=leetcode.cn id=652 lang=golang
 *
 * [652] 寻找重复的子树
 */
package Solutions

// @lc code=start
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */

type searchTreeNode struct {
	Flag  bool
	P     *TreeNode
	child map[int]*searchTreeNode
}

func findDuplicateSubtrees(root *TreeNode) []*TreeNode {
	parentSearchNode := &searchTreeNode{}
	parentSearchNode.child = map[int]*searchTreeNode{}
	tNode := &TreeNode{
		Val:  -1,
		Left: root,
	}
	root = tNode
	var buildSearchTree = func(arr []int, node *TreeNode, n *searchTreeNode) (bool, *searchTreeNode) {
		for _, v := range arr {
			if tN, ok := n.child[v]; ok {
				n = tN
			} else {
				tN = &searchTreeNode{
					child: make(map[int]*searchTreeNode),
				}
				n.child[v] = tN
				n = tN
			}

		}
		if n.P == nil || n.Flag {
			n.P = node
			return false, n
		} else {
			n.Flag = true
			return true, n
		}
	}
	var ans = make([]*TreeNode, 0, 8)
	var f func(r *TreeNode) ([]int, *searchTreeNode)
	f = func(r *TreeNode) ([]int, *searchTreeNode) {
		var arr []int
		var sn *searchTreeNode = parentSearchNode
		var leftRange []int
		if r.Left != nil {
			leftRange, sn = f(r.Left)
		}
		arr = append(arr, r.Val)
		if r.Right != nil {
			rightRange, _ := f(r.Right)
			arr = append(arr, 202)
			arr = append(arr, rightRange...)
		}
		// fmt.Println(leftRange)
		ok, tns := buildSearchTree(arr, r, sn)
		if ok {
			ans = append(ans, r)
		}
		sn = tns

		leftRange = append(leftRange, arr...)
		return leftRange, sn
	}
	f(root)
	return ans

}

// @lc code=end
